\section{Применение к задаче коммивояжера}
\subsection{Постановка задачи}
Дан полный взвешенный граф $G$, требуется найти в нем гамильтонов цикл минимальной стоимости. Минимальная стоимость определяется суммой
весов всех ребер, входящих в гамильтонов цикл.
\subsection{Кодирование решения}
Чтобы к задаче можно было применить алгоритм имитации отжига требуется закодировать решение. Кодирование для этой задачи очечидно:
каждому маршруту коммивояжера сопоставим кортеж $(a_1, a_2,\ldots,a_n)$, который характеризует последовательность обхода вершин в графе.
\subsection{Начальное решение}
Есть несколько техник найти начальное решение для задачи коммивояжера (например, \flqqближайшая вставка\frqq или \flqqостовный обход\frqq),
которые на метрических графах даже дадут решение отличающееся не более чем в два раза от оптимального. Но мне было интересно, сможет ли
алгоритм найти достаточно хорошее решение из достаточно плохого, поэтому в качестве начального решения я использую кортеж
$(1, 2,\ldots,n)$.


\subsection{Изменение решения}
Изменения текущего решения осуществляется следующим образом: случайно выбираются вершины $a_i$ и $a_j$, которые затем переставляются.
То есть $(a_1, a_2,\ldots{}a_i\ldots{}a_j\ldots,a_n) \rightarrow (a_1, a_2,\ldots{}a_j\ldots{}a_i\ldots,a_n)$.

\subsection{Установка параметров}
Нижеследующие параметры вычислены эмпирически, ни в коем случае не утверждается, что они являются для данной задачи оптимальными.
\begin{description}
 \item[Начальное значение $T$.] Будут приняты 30\% плохих решений, отличающихся от $F(\overline{X}_0)$ не более чем на 15\%.
 \item[Число изменений решения на одной температурной стадии] равно 400$n$, где $n$ - число степеней свободы.
 \item[Закон изменения температуры.] $T_{n+1} = 0.98T_n$
 \item[Условие остановки алгоритма.] Остановка по 20 безрезультатным понижениям температуры.
\end{description}

\subsection{Результаты тестов}
Тестовые графы \cite{tsplib} являются \flqqгеографическими\frqq, т.е. они  заданы списками координат вершин, а расстояние между ними задается обычной
евклидовой метрикой. Выбор именно такого типа графов был обусловлен наглядностью получаемых для них решений.
Для каждого графа из набора тестов известен также его оптимальный маршрут, что позволяет вычислить отклонение приближенного решения.
Для сравнения, для графов малых размерностей (до 14 вершин) также оптимальное решение было найдено полным перебором. Результаты тестирования 
можно увидеть в таблице \ref{tab:bruteforce}, а этапы работы алгоритма на больших графах на рисунках \ref{img:first}-\ref{img:last}.

Параллельный вариант алгоритма с помощью NVIDIA~CUDA работает в среднем в 5 раз быстрее, но сделать так, чтобы найденные решения были
не хуже решений последовательного варианта, мне не удалось: наблюдается ухудшение решения примерно на 50\%.

\begin{table}[H]
\caption{\label{tab:bruteforce}Сравнение с полным перебором.}

\begin{tabular}{|c|l|l|c|}
\hline
Число     & Полный        &Моделирование & Отклонение от \\
вершин    & перебор, с   &отжига, с    & оптимального решения, \%\\
\hline
10   &   0.03   &   0.8   &   0\%\\
\hline
11   &   0.312  &   1.01  &   0\%\\
\hline
12   &   3.6 &   1.1  &   0\%\\
\hline
13   &   46.0&   1.3  &   0\%\\
\hline
14   &   630.1&  1.4  &   0\%\\
\hline
15   &   -     &  1.8  &   0\%\\
\hline
16   &   -     &  2.2  &   0\%\\
\hline
24   &   -     &  4.1  &   0 - 0.3\%\\
\hline
48   &   -     &  18.5  &   0 - 2\%\\
\hline
100  &   -     &  82.6  &   4 - 8\%\\
\hline
280  &   -     &  576.2 &   17 - 29\%\\
\hline
442  &   -     &  2197.2  & 20 - 24\%\\
\hline
\end{tabular}
\end{table}

\begin{figure}[H]
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{att48_worse_pub}} 1-ая итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{att48_middle_pub}} 147-ая итерация \\
\end{minipage}
\vfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{att48_better_pub}} 193-я  итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{att48_best_pub}} 387-ая итерация \\
\end{minipage}
\caption{\label{img:first}Граф размерностью 48 вершин. За 387 итераций (понижений температуры) алгоритм нашел оптимальное решение.}
\end{figure}




\begin{figure}[H]
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{kroA100_worse_pub}} 1-ая итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{kroA100_middle_pub}} 170-ая итерация\\
\end{minipage}
\vfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{kroA100_better_pub}} 237-ая итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{kroA100_best_pub}} 422-ая итерация \\
\end{minipage}
\caption{Граф размерностью 100 вершин. За 422 итерации алгоритм нашел приближенное решение, отличающееся от оптимального на 4\%}
\end{figure}


\begin{figure}[H]
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{a280_worse_pub}} 1-ая итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{a280_middle_pub}} 134-ая итерация \\
\end{minipage}
\vfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{a280_better_pub}} 195-ая итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{a280_best_pub}} 419-ая итерация \\
\end{minipage}
\caption{Граф размерностью 280 вершин. За 419 итераций алгоритм нашел приближенное решение, отличающееся от оптимального на 17\%}
\end{figure}


\begin{figure}[H]
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{pcb442_worse_pub}} 1-ая итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{pcb442_middle_pub}} 260-ая итерация\\
\end{minipage}
\vfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{pcb442_better_pub}} 292-ая итерация \\
\end{minipage}
\hfill
\begin{minipage}[h]{0.47\linewidth}
\center{\includegraphics[width=1\linewidth]{pcb442_best_pub}} 561-ая итерация \\
\end{minipage}
\caption{\label{img:last}Граф размерностью 442 вершин. За 561 итерацию алгоритм нашел приближенное решение, отличающееся от оптимального на 20\%}
\end{figure}

